import java.text.SimpleDateFormat;
import java.util.Date;

public class Quicksort {
    public static void main(String[] args) {
        int[] arr=new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i]=(int) (Math.random()*80000);
        }
        int[] temp=new int[arr.length];
        int right=arr.length;
        int left=0;
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSSS");
        String s1 = simpleDateFormat.format(date1);
        System.out.println("排序前：" + s1);
        Quicksort(arr,left,right-1,temp);
        Date date2 = new Date();
        String s2 = simpleDateFormat.format(date2);
        System.out.println("排序后：" + s2);

    }
    public static void Quicksort(int[] arr, int left, int right, int[] temp){
    if (left<right){
        int mid=(left+right)/2;
        Quicksort(arr,left,mid,temp);
        Quicksort(arr,mid+1,right,temp);
        Quicksort1(arr,left,mid,right,temp);
    }

    }
    public static void Quicksort1(int[] arr, int left,int mid, int right, int[] temp){
        int i=left;
        int j=mid+1;
        int index=0;

        while (i<=mid&&j<=right){
            if (arr[i]<=arr[j]){
                temp[index]=arr[i];
                index++;
                i++;
            }else {
                temp[index]=arr[j];
                index++;
                j++;
            }
        }
        while (i<=mid){
            temp[index]=arr[i];
            index++;
            i++;
        }
        while (j<=right){
            temp[index]=arr[j];
            index++;
            j++;
        }
        index=0;
        int tempindex=left;
        while (tempindex<=right){
            arr[tempindex]=temp[index];
            index++;
            tempindex++;
        }
    }
}
